#pragma once

struct ListNode {
	int val;
	ListNode* next;
	ListNode(int x) : val(x), next(/*NULL*/nullptr) {}
};

class Solution {
public:
	ListNode* reverseList1(ListNode* head)
	{

		if (!head || !head->next)
		{
			return head;
		}

		ListNode* prevNode = nullptr, * nextNode = nullptr;

		while (head->next)
		{
			nextNode = head->next;
			head->next = prevNode;
			prevNode = head;
			head = nextNode;
		}

		head->next = prevNode;
		return head;
	}

	ListNode* reverseList2(ListNode* head) 
	{
		if (!head || !head->next)
		{
			return head;
		}

		ListNode* last = reverseList2(head->next);

		head->next->next = head;
		head->next = nullptr;
		return last;
	}
};

